
class BalancedExpression(object):
    
    class Match(object):
        def __init__(self, groups, groupdict={}):
            self._groups = groups
            self._groupdict = groupdict
        def group(self, index=0):
            return self._groups[index]
        def groups(self):
            return self._groups
        def groupdict(self):
            return self._groupdict
        def __repr__(self):
            return "<Balanced match: %s>" % \
                ",".join(`x` for x in self._groups)
    
    def __init__(self, list_of_parens=[('(', ')')], repeating=False):
        self.parens = list_of_parens
        self.repeating = repeating
        
    def match(self, text):
        stack = []
        open_close = dict(self.parens)
        close = set(open_close.values())
        group = []
        for c in text:
            group.append(c)
            if c in open_close:
                stack.append(open_close[c])
            elif c in close:
                if stack and stack[-1] == c:
                    stack.pop()
                    if not stack and not self.repeating: break
                else:
                    return None # mismatched parenthesis
        else:
            if stack:
                return None # missing close parenthesis
        
        return self.Match(["".join(group)])
    
    @classmethod
    def compile(cls, string):
        parens = []
        repeating = False
        while string:
            if string == '*':
                repeating = True
                break
            parens.append(tuple(string[:2]))
            string = string[2:]
        return cls(parens, repeating)
    
    def __repr__(self):
        star = self.repeating and '*' or ''
        return " x ".join("/%s...%s%s/" % (paren[0],paren[1],star) for paren in self.parens)
    
    
class BothExpressions(object):
    
    def __init__(self, expressions):
        self.expressions = expressions
        
    def match(self, text):
        x = None
        for expr in self.expressions:
            mo = expr.match(text)
            if mo is None:
                return None
            else:
                text = mo.group()
                if x is None or x.group() != text:
                    x = mo
        return x
    
    def __repr__(self):
        return " & ".join(`x` for x in self.expressions)
    

if __name__ == '__main__':
    import re
    
    bp = BalancedExpression.compile("()")
    bp_rep = BalancedExpression.compile("()*")
    bpc = BalancedExpression([tuple('()'), tuple('{}')])
    k_bpc = BothExpressions([re.compile("k.*"), bpc])
    
    inputs = ["(1(2)3)",
              "(1(2)3) (4)",
              "(1(2)3)(4)",
              "k (1(2)3)",
              "k (1(2{)}3)",
              "(1",
              "3)"]
    
    for expr in [bp, bp_rep, bpc, k_bpc]:
        print expr
        for input in inputs:
            print "  ", input, expr.match(input)
